{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Domino and Tromino Tiling"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numTilings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #多米诺和托米诺平铺"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有两种形状的瓷砖：一种是&nbsp;<code>2 x 1</code> 的多米诺形，另一种是形如&nbsp;\"L\" 的托米诺形。两种形状都可以旋转。</p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/07/15/lc-domino.jpg\" style=\"height: 195px; width: 362px;\" /></p>\n",
    "\n",
    "<p>给定整数 n ，返回可以平铺&nbsp;<code>2 x n</code> 的面板的方法的数量。<strong>返回对</strong>&nbsp;<code>10<sup>9</sup>&nbsp;+ 7</code>&nbsp;<strong>取模&nbsp;</strong>的值。</p>\n",
    "\n",
    "<p>平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/07/15/lc-domino1.jpg\" style=\"height: 226px; width: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 3\n",
    "<strong>输出:</strong> 5\n",
    "<strong>解释:</strong> 五种不同的方法如上所示。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 1\n",
    "<strong>输出:</strong> 1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [domino-and-tromino-tiling](https://leetcode.cn/problems/domino-and-tromino-tiling/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [domino-and-tromino-tiling](https://leetcode.cn/problems/domino-and-tromino-tiling/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        @cache\n",
    "        def p(n):\n",
    "            if n == 2:\n",
    "                return 1\n",
    "            return (p(n - 1) + f(n - 2)) % MOD\n",
    "        @cache\n",
    "        def f(n):\n",
    "            if n <= 2:\n",
    "                return n\n",
    "            return (f(n - 1) + f(n - 2) + 2 * p(n - 1)) % MOD\n",
    "        return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numTilings(self, N):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :rtype: int\n",
    "        35MS\n",
    "        \"\"\"\n",
    "        if N == 1:\n",
    "            return 1\n",
    "        if N == 2:\n",
    "            return 2\n",
    "        dp = [1 for _ in range(N + 1)]\n",
    "        dp[2] = 2\n",
    "        for i in range(3, N + 1):\n",
    "            dp[i] = (2 * dp[i - 1] + dp[i - 3]) % int(1e9 + 7)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, N):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dp1, dp2 = [1, 1], [0]\n",
    "        for n in range(2, N + 1):\n",
    "            dp1.append(dp1[-2] + dp1[-1] + dp2[-1] * 2)\n",
    "            dp2.append(dp1[-3] + dp2[-1])\n",
    "        return dp1[N] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, N):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :rtype: int\n",
    "        :ref:https://blog.csdn.net/fuxuemingzhu/article/details/83059602\n",
    "        \"\"\"\n",
    "        dp = [[0] * 2 for _ in range(N + 1)]\n",
    "        dp[0][0] = 1\n",
    "        dp[1][0] = 1\n",
    "        for i in range(2, N + 1):\n",
    "            dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + 2 * dp[i - 1][1])\n",
    "            dp[i][1] = (dp[i - 2][0] + dp[i - 1][1])\n",
    "        return dp[-1][0]% (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, N):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 动态规划\n",
    "        # 时间复杂度：O(N)，空间复杂度：O(1)\n",
    "        # 本题既属于拆分问题，又属于需要维持两个变量的问题\n",
    "        # dp公式：\n",
    "        # dp[0][n] = dp[0][n-1] + dp[0][n-2] + 2*dp[1][n-1]\n",
    "        # dp[1][n] = dp[0][n-2] + dp[1][n-1]\n",
    "        # 其中dp[0][n]表示2*n的面板的平铺方案数，dp[1][n]表示2*n但是最后一列只有一个方砖的面板的平铺方案数\n",
    "        # 下面的算法对时间复杂度进行了优化\n",
    "        if N <= 2:\n",
    "            return N\n",
    "        a_1, a_2 = 2, 1\n",
    "        b_1 = 1\n",
    "        for _ in range(3, N+1):\n",
    "            a_0 = a_1 + a_2 + 2*b_1\n",
    "            b_0 = a_2 + b_1\n",
    "            a_1, a_2 = a_0, a_1\n",
    "            b_1 = b_0\n",
    "        return a_0 % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, N: 'int') -> 'int':\n",
    "        f = [ [0, 0, 0, 0] for _ in range(N + 1) ]\n",
    "        f[0][3] = 1\n",
    "        for i in range(1, N + 1):\n",
    "            f[i][0] = f[i - 1][3]\n",
    "            f[i][1] = f[i - 1][0] + f[i - 1][2]\n",
    "            f[i][2] = f[i - 1][0] + f[i - 1][1]\n",
    "            f[i][3] = f[i - 1][3] + f[i - 1][1] + f[i - 1][2] + f[i - 1][0]\n",
    "        return f[N][3] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numTilings(self, N):\n",
    "        MOD = 10**9 + 7\n",
    "        dp = [1, 0, 0, 0]\n",
    "        for _ in range(N):\n",
    "            ndp = [0, 0, 0, 0]\n",
    "            ndp[0] = (dp[0] + dp[3]) % MOD\n",
    "            ndp[1] = (dp[0] + dp[2]) % MOD\n",
    "            ndp[2] = (dp[0] + dp[1]) % MOD\n",
    "            ndp[3] = (dp[0] + dp[1] + dp[2]) % MOD\n",
    "            dp = ndp\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # https://leetcode.com/problems/domino-and-tromino-tiling/discuss/156332/O(log-N)-C%2B%2B-concise-and-clean-and-easy-DP-solution_(%3Az)_\n",
    "        \n",
    "    def numTilings(self, N: int) -> int:\n",
    "        dp0=dp1=dp2=0\n",
    "        dp3=1\n",
    "        for i in range(N):\n",
    "            dp0,dp1,dp2,dp3=dp3,dp0+dp2,dp0+dp1,dp0+dp1+dp2+dp3\n",
    "        return dp3 % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, N: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        dp = [1, 0, 0, 1]\n",
    "        for i in range(1,N):\n",
    "            ndp = [0, 0, 0, 0]\n",
    "            ndp[0] = dp[3] \n",
    "            ndp[1] = (dp[0] + dp[2]) % MOD\n",
    "            ndp[2] = (dp[0] + dp[1]) % MOD\n",
    "            ndp[3] = (dp[0] + dp[1] + dp[2] + dp[3]) % MOD\n",
    "            dp = ndp\n",
    "\n",
    "        return dp[3]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, N: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        dp = [1, 0, 0, 0]\n",
    "        for _ in range(N):\n",
    "            ndp = [0, 0, 0, 0]\n",
    "            ndp[0b00] = (dp[0b00] + dp[0b11]) % MOD\n",
    "            ndp[0b01] = (dp[0b00] + dp[0b10]) % MOD\n",
    "            ndp[0b10] = (dp[0b00] + dp[0b01]) % MOD\n",
    "            ndp[0b11] = (dp[0b00] + dp[0b01] + dp[0b10]) % MOD\n",
    "            dp = ndp\n",
    "\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, N: int) -> int:\n",
    "        \"\"\"\n",
    "            For a generic problem we need to do a memorized search, but for this one we don't have to. \n",
    "\n",
    "            The reason why this problem is easier is because we only need to fill a 2*N space. Since there\n",
    "            are only two types of shapes and they both have a height of 2, it is not hard to figure out we\n",
    "            should construct a DP based on the status of each column. Each column can be in either of the \n",
    "            following four states:\n",
    "                0. Not filled;\n",
    "                1. Top filled, bottom not filled;\n",
    "                2. Top not filled, bottom filled;\n",
    "                3. Completely filled. \n",
    "            \n",
    "            If we have the status of the previous column, we can play with the blocks and figure out how we\n",
    "            can transit to the state of the current column. Notice that each column must be completely filled,\n",
    "            so many combinations can be ruled out. \n",
    "\n",
    "                State 0: can go to all four states;\n",
    "                State 1: can go to state 2 or 3;\n",
    "                State 2: can go to state 1 or 3;\n",
    "                State 3: can only go to state 0 because we don't want to fill up the next next column (yet)\n",
    "            \n",
    "            For each state, we just need to sum up the counts from all possible previous states. In the solution\n",
    "            below, our mini DP table tracks the status of the current column, so the base solutions (when the board\n",
    "            is completely not filled) would be:\n",
    "\n",
    "                State 0: 1 because we have exactly one way of letting the board reach this condition (not doing anything)\n",
    "                State 1, 2, 3: 0 because we don't have any way to get the board to these states\n",
    "            \n",
    "            Our final solution would be DP[N][0] = DP[N-1][3]. \n",
    "\n",
    "            In a more generic case where the block has a maximum width of M, we can use a similar method, but track the \n",
    "            previous M columns. It will be pretty complicated and may not be better than a memorized DFS. \n",
    "        \"\"\"\n",
    "        \n",
    "        not_filled_cnt = 1\n",
    "        top_filled_cnt = 0\n",
    "        bot_filled_cnt = 0\n",
    "        all_filled_cnt = 0\n",
    "        MOD_NUM = 10**9 + 7\n",
    "        for i in range(N):\n",
    "            n0 = (not_filled_cnt + all_filled_cnt) % MOD_NUM\n",
    "            n1 = (not_filled_cnt + bot_filled_cnt) % MOD_NUM\n",
    "            n2 = (not_filled_cnt + top_filled_cnt) % MOD_NUM\n",
    "            n3 = (not_filled_cnt + top_filled_cnt + bot_filled_cnt) % MOD_NUM\n",
    "            not_filled_cnt, top_filled_cnt, bot_filled_cnt, all_filled_cnt = n0, n1, n2, n3\n",
    "        \n",
    "        return not_filled_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, N: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        top_hiatus, bottom_hiatus, un_hiatus, hiatus = 0, 0, 1, 1\n",
    "        for _ in range(1, N):\n",
    "            top_hiatus, bottom_hiatus, un_hiatus, hiatus = (hiatus + top_hiatus) % mod, (hiatus + bottom_hiatus) % mod, \\\n",
    "                                                           (un_hiatus + top_hiatus + bottom_hiatus + hiatus) % mod, un_hiatus % mod\n",
    "        return un_hiatus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, N: int) -> int:\n",
    "        dp=[1,0,0,1]\n",
    "        for i in range(1,N):\n",
    "            tmp=[0,0,0,0]\n",
    "            tmp[0]=dp[3]%(10**9+7)\n",
    "            tmp[1]=(dp[0]+dp[2])%(10**9+7)\n",
    "            tmp[2]=(dp[0]+dp[1])%(10**9+7)\n",
    "            tmp[3]=(dp[3]+dp[0]+dp[1]+dp[2])%(10**9+7)\n",
    "            dp=tmp[:]\n",
    "        return dp[3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, N: int) -> int:\n",
    "        if N <= 1:\n",
    "            return N\n",
    "        dp = [[0] * 2 for _ in range(N)]\n",
    "        dp[0][0] = 0\n",
    "        dp[0][1] = 1\n",
    "        dp[1][0] = 1\n",
    "        dp[1][1] = 2\n",
    "        MOD = 10 ** 9 + 7\n",
    "        for i in range(2, N):\n",
    "            dp[i][0] = (dp[i - 1][0] + dp[i - 2][1]) % MOD\n",
    "            dp[i][1] = (dp[i - 1][1] + 2 * dp[i - 1][0] + dp[i - 2][1]) % MOD\n",
    "        return dp[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, N: int) -> int:\n",
    "        \"\"\"\n",
    "        2维DP，Time O(N), Space O(N)\n",
    "        dp[i][0] = dp[i-1][0] + dp[i-2][0] + 1*dp[i-1][1]\n",
    "        dp[i][1] = dp[i-2][0] + dp[i-1][1]\n",
    "        \"\"\"\n",
    "        kMod = 1e9 + 7\n",
    "        dp = collections.defaultdict(int)\n",
    "        dp[0, 1] = dp[1, 1] = 0  # 初始化边界条件\n",
    "        dp[0, 0] = dp[1, 0] = 1  # 完整覆盖0个或1个column均为1个解\n",
    "        for i in range(2, N+1):\n",
    "            dp[i, 0] = (dp[i-1, 0] + dp[i-2, 0] + 2 * dp[i-1, 1]) % kMod\n",
    "            dp[i, 1] = (dp[i-2, 0] + dp[i-1, 1]) % kMod\n",
    "        return int(dp[N, 0])  # 完整覆盖N个column并且没有多出一块的解的个数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, N: int) -> int:\n",
    "        \n",
    "        f1=[0,1,2]\n",
    "        e1=[0,0,1]\n",
    "        e2=[0,0,1]\n",
    "        i=2\n",
    "        while i<=N:\n",
    "            if(i>=len(f1)):\n",
    "                f1.append(f1[i-1]+f1[i-2]+e1[i-1]+e1[i-1])\n",
    "            if(i>=len(e1)):\n",
    "                e1.append(f1[i-2]+e2[i-1])\n",
    "                e2.append(f1[i-2]+e1[i-1])  \n",
    "            i+=1\n",
    "        print(f1)\n",
    "        return f1[N]%(10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, N: int, d=None, dd=None) -> int:\n",
    "        if d is None:\n",
    "            d = {-2:0, -1:0, 0:1}\n",
    "            dd = {-2:0, -1:0, 0:1}\n",
    "        if N in d:\n",
    "            return d[N]\n",
    "        d[N] = (self.numTilings(N - 1, d, dd) + self.numTilings(N - 2, d, dd) + dd[N - 3] * 2) % (10 ** 9 + 7)\n",
    "        # print(d)\n",
    "        dd[N] = dd[N - 1] + d[N]\n",
    "        return d[N]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, N: int) -> int:\n",
    "        # state0 -> 都空\n",
    "        # state1 -> 第一行有瓷砖\n",
    "        # state2 -> 第二行有瓷砖\n",
    "        # state3 -> 都有瓷砖\n",
    "        # 初始化考虑只有一列\n",
    "        dp = [1, 0, 0, 1]\n",
    "        for i in range(2, N+1):\n",
    "            dpn = [0, 0, 0, 0]\n",
    "            dpn[0] = dp[3] # 只能从满 什么都不贴转移\n",
    "            dpn[1] = dp[0] + dp[2] # 空的贴一个托米诺\n",
    "            dpn[2] = dp[0] + dp[1] # 空的贴一个托米诺\n",
    "            dpn[3] = dp[0] + dp[1] + dp[2] + dp[3]\n",
    "            dp = dpn \n",
    "        return dp[3] % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, n: int) -> int:\n",
    "        if n == 1: return 1\n",
    "        f = [0] * (n + 1)\n",
    "        f[0] = f[1] = 1\n",
    "        f[2] = 2\n",
    "        for i in range(3, n + 1):\n",
    "            f[i] = (f[i - 1] * 2 + f[i - 3]) % MOD\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, n: int) -> int:\n",
    "        # 找规律发现....\n",
    "        MOD = 10**9 + 7\n",
    "        if n==1: return 1\n",
    "\n",
    "        f = [0] * (n+1)\n",
    "        f[0] = f[1] = 1\n",
    "        f[2] = 2\n",
    "        for i in range(3, n+1):\n",
    "            f[i] = (2*f[i-1] + f[i-3]) % MOD\n",
    "        return f[n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, n: int) -> int:\n",
    "        if(n <= 2):return n\n",
    "        result = [0 for i in range(n + 1)]\n",
    "        result[0] = 1\n",
    "        result[1] = 1\n",
    "        result[2] = 2\n",
    "        for i in range(3,n+1):\n",
    "            result[i] += result[i-1]\n",
    "            result[i] += result[i-2]\n",
    "            n = 3\n",
    "            while(i - n >=0):\n",
    "                result[i] += 2* result[i-n]\n",
    "                n += 1\n",
    "        return result[-1]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, n: int) -> int:\n",
    "        if n == 0 :return 0\n",
    "        s = [[0]*4 for _ in range(n+1)]\n",
    "        s[0][3] = 1\n",
    "        for i in range(1,n+1):\n",
    "            s[i][0] = s[i-1][3]\n",
    "            s[i][1] = s[i-1][0] + s[i-1][2]\n",
    "            s[i][2] = s[i-1][0] + s[i-1][1]\n",
    "            s[i][3] = s[i-1][0] +s[i-1][1]+s[i-1][2]+s[i-1][3]\n",
    "        return s[-1][3] % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, n: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        dp = [[0]*4 for _ in range(n+1)]\n",
    "        dp[0][0] = 0\n",
    "        dp[0][1] = 0\n",
    "        dp[0][2] = 0\n",
    "        dp[0][3] = 1\n",
    "        for i in range(1, n+1):\n",
    "            dp[i][0] = dp[i-1][3]\n",
    "            dp[i][1] = dp[i-1][0] + dp[i-1][2]\n",
    "            dp[i][2] = dp[i-1][0] + dp[i-1][1]\n",
    "            dp[i][3] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]\n",
    "        return dp[n][3]%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, n: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0], dp[1] = 1, 1\n",
    "        \n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = (2 * dp[i-1] + dp[i-3]) % MOD\n",
    "        \n",
    "        return dp[n]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, n: int) -> int:\n",
    "        mod=10**9+7\n",
    "        if n==1:return 1\n",
    "        dp=[0]*(n+1)\n",
    "        dp[0]=dp[1]=1\n",
    "        dp[2]=2\n",
    "        for i in range(3,n+1):\n",
    "            dp[i]=(dp[i-1]*2+dp[i-3])%mod\n",
    "        return dp[n]    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, n: int) -> int:\n",
    "        # f(0) = 1\n",
    "        # f(1) = 1\n",
    "        # f(2) = 2\n",
    "        \n",
    "        # f(3) = f(2) + f(1) + 2*f(0)\n",
    "        #      = 2 + 1 + 2*1 = 5\n",
    "        # f(4) = f(3) + f(2) + 2*f(1)\n",
    "        #      =  5 + 2 + 2*1\n",
    "        f = [0] * (n+1)\n",
    "        f[0:3] = [1,1,2]\n",
    "        for i in range(3, n+1):\n",
    "            f[i] = f[i-1] + f[i-2] + \\\n",
    "                   2 * sum(f[i-3-k] for k in range(0, i-2, 2)) + \\\n",
    "                   2 * sum(f[i-2-k] for k in range(2, i-1, 2))\n",
    "            # print(i, [f[i-2-k] for k in range(2, i-1, 2)])\n",
    "        # print(f)\n",
    "        \n",
    "        return f[n] % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilings(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [[0] * 4 for _ in range(n + 1)]\n",
    "        dp[0][3] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i][0] = dp[i - 1][3]\n",
    "            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD\n",
    "            dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD\n",
    "            dp[i][3] = (((dp[i - 1][0] + dp[i - 1][1]) % MOD + dp[i - 1][2]) % MOD + dp[i - 1][3]) % MOD\n",
    "        return dp[n][3]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
